package com.剑指offer.第一章;

/**
 * 字符串中的字符都是小写
 * 输入一个字符串数组words，请计算不包含想同字符的两个字符串words[i]和word[j]的长度乘积的最大值
 */
public class 单词长度的最大乘积 {

    /**
     * 使用int型整数的二进制形式有32位，但只需要26位就能表示一个字符串中出现的字符
     *
     * @param words
     * @return
     */
    public static int resolve(String[] words) {
        int[] ints = new int[words.length];
        // 记录每个字符串中的字符是否出现过
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                ints[i] = ints[i] | (1 << (c - 'a'));
            }
        }
        int result = 0;
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((ints[i] & ints[j]) == 0) {
                    int length = words[i].length() * words[j].length();
                    result = Math.max(result, length);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(resolve(new String[]{"abcw", "foo", "bar", "fxyz", "abcdef"}));
    }

}
